package com.yitiao.data_algorithms.leetcode.editor.cn;

import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.TreeNode;

class RemoveDuplicatesFromSortedList {
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        // 题目数据保证链表已经按升序 排列
        public ListNode deleteDuplicates(ListNode head) {
            // 特例返回
            if (head==null) return null;
            // 虚拟头结点，只是返回用
            ListNode dummy = new ListNode(0, head);
            // 第一个初始值
            int init = head.val;
            // 遍历迭代
            while (head.next != null) {
                // 保存上一个结点
                ListNode prev = head;
                // head 指向下一个结点
                head = head.next;
                // 下一个的值和上一个比较
                if (head.val == init) {
                    // 删除下一个结点
                    prev.next = head.next;
                    // 头结点指回到上一个 对应下次的 head = head.next;
                    head =prev;
                } else {
                    // 不相同，那对比值移到下一个
                    init = head.val;
                }
            }
            return dummy.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}